// Copyright (c) 2020-present, INSPUR Co, Ltd. All rights reserved.
// This source code is licensed under Apache 2.0 License.
//
// Created by florian on 05.08.15.

#include "tree_node.h"
#include <algorithm>
#include <assert.h>
#include <emmintrin.h> // x86 SSE intrinsics

namespace syn_art_fullkey {

bool N16::insert(uint8_t key, N *n) {
  if (count_ >= 16)
    return false;
  keys_[count_].store(flipSign(key), std::memory_order_release);
  children_[count_].store(n, std::memory_order_release);
  count_++;
  return true;
}

void N16::change(uint8_t key, N *val) {
  auto childPos = getChildPos(key);
  assert(childPos != nullptr);
  return childPos->store(val, std::memory_order_release);
}

std::atomic<N *> *N16::getChildPos(const uint8_t k) {
  __m128i cmp =
      _mm_cmpeq_epi8(_mm_set1_epi8(flipSign(k)),
                     _mm_loadu_si128(reinterpret_cast<const __m128i *>(keys_)));
  unsigned bitfield = _mm_movemask_epi8(cmp) & ((1 << count_) - 1);
  while (bitfield) {
    uint8_t pos = ctz(bitfield);

    if (children_[pos].load() != nullptr) {
      return &children_[pos];
    }
    bitfield = bitfield ^ (1 << pos);
  }
  return nullptr;
}

N *N16::getChild(const uint8_t k) const {
  __m128i cmp =
      _mm_cmpeq_epi8(_mm_set1_epi8(flipSign(k)),
                     _mm_loadu_si128(reinterpret_cast<const __m128i *>(keys_)));
  unsigned bitfield = _mm_movemask_epi8(cmp) & ((1 << 16) - 1);
  while (bitfield) {
    uint8_t pos = ctz(bitfield);

    N *child = children_[pos].load();
    if (child != nullptr && keys_[pos].load() == flipSign(k)) {
      return child;
    }
    bitfield = bitfield ^ (1 << pos);
  }
  return nullptr;
}

void N16::getChildrenSmall(uint8_t start, uint8_t end,
                           std::tuple<uint8_t, N *> *&childrenList,
                           uint32_t &childrenCount, u_int32_t childMax) const {
  childrenCount = 0;
  uint32_t i = 0, j = 0, needMoveNum = 0;
  for (i = 0; i < count_; ++i) {
    uint8_t key = flipSign(this->keys_[i]);
    if (key >= start && key <= end) {
      N *child = this->children_[i].load();
      if (child != nullptr) {
        for (j = 0; j < childrenCount; ++j) {
          if (std::get<0>(childrenList[j]) > key)
            break;
        }
        if (j >= childMax)
          continue;
        needMoveNum = childrenCount - j;
        if (j <= childMax - 2 && needMoveNum > 0) {
          memcpy(&(childrenList[j + 1]), &(childrenList[j]),
                 sizeof(std::tuple<uint8_t, N *>) * (childMax - j - 1));
        }
        childrenList[j] = std::make_tuple(key, child);
        if (childrenCount < childMax)
          childrenCount++;
      }
    }
  }
}
void N16::getChildrenLarge(uint8_t start, uint8_t end,
                           std::tuple<uint8_t, N *> *&childrenList,
                           uint32_t &childrenCount, u_int32_t childMax) const {
  childrenCount = 0;
  uint32_t i = 0, j = 0, needMoveNum = 0;
  for (i = 0; i < count_; ++i) {
    uint8_t key = flipSign(this->keys_[i]);
    if (key >= start && key <= end) {
      N *child = this->children_[i].load();
      if (child != nullptr) {
        for (j = 0; j < childrenCount; ++j) {
          if (std::get<0>(childrenList[j]) > key)
            break;
        }
        if (childrenCount == childMax) {
          if (j == 0)
            continue;
          if (j >= 2) {
            memcpy(&(childrenList[0]), &(childrenList[1]),
                   sizeof(std::tuple<uint8_t, N *>) * (j - 1));
          }
          childrenList[j - 1] = std::make_tuple(key, child);
        } else {
          needMoveNum = childrenCount - j;

          if (needMoveNum > 0) {
            memcpy(&(childrenList[j + 1]), &(childrenList[j]),
                   sizeof(std::tuple<uint8_t, N *>) * (needMoveNum >= childMax
                                                           ? (childMax - 1)
                                                           : needMoveNum));
          }
          childrenList[j] = std::make_tuple(key, child);
          if (childrenCount < childMax)
            childrenCount++;
        }
      }
    }
  }
}

} // namespace syn_art_fullkey